#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <dirent.h>

typedef struct {
    int weight;
    double value;
    int index;
} Item;

Item* read_knapsack_file(const char* filename, int* n, int* capacity) {
    FILE* fp = fopen(filename, "r");
    if (!fp) {
        printf("无法打开文件：%s\n", filename);
        return NULL;
    }
    fscanf(fp, "%d %d", n, capacity);
    Item* items = (Item*)malloc(sizeof(Item) * (*n));
    for (int i = 0; i < *n; i++) {
        fscanf(fp, "%d %lf", &items[i].weight, &items[i].value);
        items[i].index = i + 1;
    }
    fclose(fp);
    return items;
}

double best_value = 0;
int* best_solution = NULL;

void brute_force(Item* items, int n, int capacity, int i, int curr_weight, double curr_value, int* solution) {
    if (i == n) {
        if (curr_weight <= capacity && curr_value > best_value) {
            best_value = curr_value;
            memcpy(best_solution, solution, n * sizeof(int));
        }
        return;
    }

    solution[i] = 0;
    brute_force(items, n, capacity, i + 1, curr_weight, curr_value, solution);

    if (curr_weight + items[i].weight <= capacity) {
        solution[i] = 1;
        brute_force(items, n, capacity, i + 1,
                    curr_weight + items[i].weight,
                    curr_value + items[i].value, solution);
    }
}

int main() {
    FILE* out = fopen("results_bruteforce.csv", "w");
    fprintf(out, "filename,n,capacity,total_value,time_ms\n");

    DIR* dir = opendir(".");
    struct dirent* entry;

    while ((entry = readdir(dir)) != NULL) {
        if (strstr(entry->d_name, "knapsack_") && strstr(entry->d_name, ".txt")) {
            int n, capacity;
            Item* items = read_knapsack_file(entry->d_name, &n, &capacity);
            if (!items) continue;

            int* solution = (int*)calloc(n, sizeof(int));
            best_solution = (int*)calloc(n, sizeof(int));
            best_value = 0;

            printf("蛮力法开始处理文件：%s（物品数=%d，容量=%d）\n", entry->d_name, n, capacity);

            clock_t start = clock();
            brute_force(items, n, capacity, 0, 0, 0.0, solution);
            clock_t end = clock();

            double elapsed = (end - start) * 1000.0 / CLOCKS_PER_SEC;

            printf("完成文件：%s\n", entry->d_name);
            printf("最大总价值：%.2f，执行时间：%.2f ms\n\n", best_value, elapsed);

            fprintf(out, "%s,%d,%d,%.2f,%.2f\n", entry->d_name, n, capacity, best_value, elapsed);

            free(solution);
            free(best_solution);
            free(items);
        }
    }

    fclose(out);
    closedir(dir);
    printf("所有文件已处理完毕，结果保存在 results_bruteforce.csv\n");
    return 0;
}
